package com.wujunshen.algorithm.leetcode.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/30 20:53<br>
 */
public class N皇后 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solveNQueens = new ArrayList<>();

        String[][] board = new String[n][n];

        Set<Integer> col = new HashSet<>();
        Set<Integer> posDaig = new HashSet<>();
        Set<Integer> negDiag = new HashSet<>();

        backTracking(0, n, solveNQueens, board, col, posDaig, negDiag);
        return solveNQueens;
    }

    public void backTracking(int row, int n, List<List<String>> solveNQueens, String[][] board, Set<Integer> col,
                             Set<Integer> posDaig, Set<Integer> negDiag) {
        if (row == n) {
            solveNQueens.add(new ArrayList<>(populate(board, n)));
            return;
        }

        for (int c = 0; c < n; c++) {
            if (col.contains(c) || posDaig.contains(row + c) || negDiag.contains(row - c)) {
                board[row][c] = ".";
                continue;
            }

            board[row][c] = "Q";
            col.add(c);
            posDaig.add(row + c);
            negDiag.add(row - c);

            backTracking(row + 1, n, solveNQueens, board, col, posDaig, negDiag);

            board[row][c] = ".";
            col.remove(c);
            posDaig.remove(row + c);
            negDiag.remove(row - c);
        }
    }

    public List<String> populate(String[][] board, int n) {
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringBuilder tmp = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (board[i][j] == null) {
                    board[i][j] = ".";
                }
                tmp.append(board[i][j]);
            }

            ans.add(tmp.toString());
        }
        return ans;
    }
}
